package j2024.j202411;

//import j2024.j202407.ListNode;
class ListNode {
    int val;
    ListNode next;
    ListNode(int x) {
        val = x;
        next = null;
    }
}
public class j1105 {
    public int searchInsert(int[] nums, int target) {
        int left = 0,right = nums.length-1;
        while(left < right){
            int mid = left + (right-left)/2;
            if(nums[mid] < target){
                left = mid+1;
            }else {
                right = mid;
            }
        }
        if(nums[left]<target){
            return left+1;
        }
        return left;
    }

    public boolean hasCycle(ListNode head) {
        ListNode slow = head,fast = head;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                return true;
            }
        }
        return false;
    }

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode ret = new ListNode(-1);
        ListNode cur = ret;
        int tmp = 0;
        while(l1!=null || l2!=null || tmp!=0){
            if(l1!=null){
                tmp+=l1.val;
                l1 = l1.next;
            }
            if(l2!=null){
                tmp += l2.val;
                l2 = l2.next;
            }
            cur.next = new ListNode(tmp%10);
            cur = cur.next;
            tmp/=10;
        }
        return ret.next;
    }
}
